package alo.p6.work3;

import alo.p6.ThreadedBinaryTreeNode;

/**
 * @ClassName InOrderSuccessor
 * @Description 在中序二叉树中查找中序后继
 * @Author Fanxc
 * @DATE 2021/2/6 10:53
 * @Version 1.0
 */
public class InorderSuccessor {

    ThreadedBinaryTreeNode inorderSuccessor(ThreadedBinaryTreeNode P){
        ThreadedBinaryTreeNode Position;
        if (P.getRtag()==1){//如果结点没有右子树，那么中序后继就是右结点
            return P.getRight();
        }else {//如果结点有右孩子，后继为右孩子的左子树的最左结点（返回左子树包含P的最近结点的左孩子结点）
            Position=P.getRight();
            while (Position.getLtag()==0){
                Position=Position.getLeft();
            }
            return Position;
        }
    }
}
